<!--
 * @Author: your name
 * @Date: 2021-08-03 17:20:25
 * @LastEditTime: 2021-08-03 17:51:17
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>插入排序</title>
</head>

<body>
  <img src="../images//insetSort.gif" alt="">

  <p>1. 从第一个元素开始，该元素可以认为已经被排序</p>
  <p>2. 取出下一个元素，在已经排序的元素序列中从后向前扫描</p>
  <p>3. 如果该元素（已排序）大于新元素，将该元素移到下一位置</p>
  <p>4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</p>
  <p>5. 将新元素插入到该位置后</p>
  <p>6. 重复步骤2~5</p>
  <script>
    /**
     * 1. 从第一个元素开始，该元素可以认为已经被排序
     * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 5. 将新元素插入到该位置后
     * 6. 重复步骤2~5
     */
    function insertSort(array) {
      const len = array.length
      for (let i = 1; i < len; i++) {
        for (let j = i; j > 0; j--) {// 在已经排序的元素序列中从后向前扫描
          if (array[j] < array[j - 1]) { // 交换两个元素的位置
            [array[j], array[j - 1]] = [array[j - 1], array[j]]
          } else {
            break
          }
        }
      }
      return array
    }
    console.log(insertSort([2, 7, 3, 1, 9, 4]))
  </script>
</body>

</html>